#460. LFU 缓存

• LeetCode：原题1
• 难度：困难
• 归类：链表（设计、哈希表、链表、双向链表）
• 主解法：双哈希表 + 双向链表

#先给结论

这道题的核心是用额外空间把查找或计数从线性扫描降为近似常数时间。面试时先说清楚“状态表示什么、为什么能排除其他候选、何时更新答案”，再写代码；只报出“用 哈希表”还不足以证明理解。

#题目描述

题目要求完成“LFU 缓存”。输入包括 inputs（integer[]）、inputs（integer[]），需要返回 list<String>。完整限制以原题为准，解题时重点利用这些特征：设计、哈希表、链表、双向链表。

示例：

输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3

#问题本质

用额外空间把查找或计数从线性扫描降为近似常数时间。需要解决的不是某个 API 的用法，而是如何用最少状态描述“已经处理什么、还剩什么”，并证明状态推进不会漏解。

#数据结构与因果链

1. 输入进入算法后，先建立 哈希表 所需的状态。
2. Map 或 Set 记录已经出现的值、频次、下标或从状态到结果的映射。
3. 先查询当前元素需要的互补信息，再按是否允许复用当前元素决定写入时机。
4. 满足终止条件后，把已经验证的状态转换成输出。

始终保持：处理当前元素前，哈希结构只包含题意允许使用的历史信息。

#示例推演

输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3

#边界与陷阱

• 空输入、单元素、重复元素以及不存在合法答案时，要有明确返回值。
• 最容易错在键的类型、重复值覆盖下标，以及查询和写入顺序导致元素自用。
• 如果实现会修改输入，面试时要主动说明；如果不能修改，则复制数据或改用额外结构。

#代码实现

参考实现来源：JoshCrozier/leetcode-javascript，按本文结构重新整理；原项目采用 MIT License。

#JavaScript 实现

/**
 * @param {number} capacity
 */
var LFUCache = function(capacity) {
  this.capacity = capacity;
  this.size = 0;
  this.minFreq = 0;
  this.values = new Map();
  this.freq = new Map();
  this.keys = new Map();
};

/**
 * @param {number} key
 * @return {number}
 */
LFUCache.prototype.get = function(key) {
  if (!this.values.has(key)) return -1;

  const freq = this.freq.get(key);
  this.freq.set(key, freq + 1);

  this.keys.get(freq).delete(key);
  if (!this.keys.get(freq).size) {
    this.keys.delete(freq);
    if (this.minFreq === freq) this.minFreq++;
  }

  if (!this.keys.has(freq + 1)) this.keys.set(freq + 1, new Set());
  this.keys.get(freq + 1).add(key);

  return this.values.get(key);
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LFUCache.prototype.put = function(key, value) {
  if (this.capacity === 0) return;

  if (this.values.has(key)) {
    this.values.set(key, value);
    this.get(key);
    return;
  }

  if (this.size === this.capacity) {
    const keyToRemove = this.keys.get(this.minFreq).values().next().value;
    this.keys.get(this.minFreq).delete(keyToRemove);
    if (!this.keys.get(this.minFreq).size) {
      this.keys.delete(this.minFreq);
    }
    this.values.delete(keyToRemove);
    this.freq.delete(keyToRemove);
    this.size--;
  }

  this.values.set(key, value);
  this.freq.set(key, 1);
  if (!this.keys.has(1)) this.keys.set(1, new Set());
  this.keys.get(1).add(key);
  this.minFreq = 1;
  this.size++;
};

#代码与思路对照

读代码时应把每个判断还原成“它排除了什么状态或完成了哪次转移”，而不是只记变量名。

#复杂度分析

• 时间复杂度：操作 get 和 put 的时间复杂度都是 O(1)。
• 空间复杂度：O(n)，其中 n 为缓存的容量。

复杂度必须按“状态数量 × 每个状态处理成本”分析；如果存在排序、堆操作、递归深度或结果数组，需要单独计入，不能只看最外层循环。

#面试官递进追问

#1. 为什么本题适合 哈希表？

因为用额外空间把查找或计数从线性扫描降为近似常数时间。 为什么问： 检查你是在识别性质，还是只凭题号背模板。回答要抓住可被利用的单调性、重复子问题或数据结构约束。

#2. 代码维护的核心状态是什么？

Map 或 Set 记录已经出现的值、频次、下标或从状态到结果的映射。 为什么问： 状态定义决定代码是否可证明。回答时要让每个变量都能对应到题意。

#3. 这个实现依赖什么不变量？

处理当前元素前，哈希结构只包含题意允许使用的历史信息。 为什么问： 不变量比逐行复述代码更能证明理解，回答要说明它在初始化、推进和结束时都成立。

#4. 为什么这样推进不会漏掉答案？

先查询当前元素需要的互补信息，再按是否允许复用当前元素决定写入时机，被跳过的状态已经由题目性质证明不可能更优或已经处理完成。 为什么问： 检查正确性证明，重点不是“指针这样写”，而是“为什么可以排除”。

#5. 最危险的边界是什么？

最容易错在键的类型、重复值覆盖下标，以及查询和写入顺序导致元素自用。 为什么问： 检查代码能否一次通过，回答要给出具体失败场景而不是只说“注意边界”。

#6. 复杂度还能优化吗？

先看瓶颈来自状态数量、每次转移成本还是辅助结构操作；只有其中一项能被减少时，复杂度才可能继续下降。 为什么问： 检查你能否从成本组成出发优化，而不是机械背最优复杂度。

#7. 如果输入规模扩大或数据改成流式，方案怎么变？

要判断当前算法是否需要随机访问全部输入；若只依赖有限历史状态，可以做滚动或在线维护，否则需要分块、外存或调整数据结构。 为什么问： 检查算法理解能否迁移到工程约束。

#8. 有哪些替代解法，如何取舍？

可以从暴力枚举开始，再比较排序、哈希、搜索或动态规划等方案；取舍标准是时间、空间、是否修改输入和实现复杂度。 为什么问： 检查横向比较能力。回答要说明替代方案为什么更慢或在什么条件下更合适。

#常见错误回答

• “这题套 哈希表 模板即可”：只有结论，没有说明题目性质和排除依据。
• 逐行朗读代码：没有建立状态、不变量和正确性因果链。
• 只报 O(n) 或 O(n²)：没有解释每个状态被访问多少次，也容易漏掉排序或辅助结构。
• 把示例能跑通当成证明：示例只能帮助检查，不能覆盖重复值、空输入和极端边界。

#可迁移总结

• 核心关键词：哈希表、状态定义、不变量、推进规则、边界。
• 一句话本质：用额外空间把查找或计数从线性扫描降为近似常数时间。
• 思考链路：识别题目性质 → 定义状态 → 证明推进安全 → 确定更新时机 → 检查边界与复杂度。
• 1 分钟回答：说清题型、核心状态、推进规则和复杂度。
• 3 分钟回答：补上正确性依据、示例和两个关键边界。
• 10 分钟回答：写出代码，并比较替代方案、空间优化和工程限制。

#刷题后自测

先只回答第 1 题，再展开后续问题：

1. 不看代码，你能用一句话说出本题的不变量吗？

2. 如果把示例中的重复值、空输入或边界值换掉，哪一行代码最先受到影响？

3. 不改变正确性的前提下，你能写出一种替代方案并比较复杂度吗？